package MyLinkedList实现;

import class自己实现链表.MyIterator;

//利用 双向链表 实现基本操作
public class MyLinkedList implements MyList {
    public MyListNode head;
    public MyListNode last;

    public MyLinkedList() {
        //MyLinkedList对象 的无参构造方法
        head=null;
        last=null;
    }

    @Override
    public boolean add(String e) {
        //O(1)
        //1.把e先装入结点中
        MyListNode node=new MyListNode(e);
        //2.将结点尾插   考虑链表为空：头结点与尾结点均指向插入的结点     链表不为空
        if(head==null) {
            head=node;
            last=node;
        }else {
            node.prev=last;
            last.next=node;
            last=node;
        }
        return true;
    }

    @Override
    public void add(int index, String e) {
        //判断下标合法性
        if(index<0 || index>size()) {
            throw new ArrayIndexOutOfBoundsException("下标不合法！");
        }

        MyListNode node=new MyListNode(e);
        //index=0即头插，需要单独处理，否则将于index=1的结果相同
        if(index==0) {
            //头插

            if(head!=null) {
                //head不为空即链表中至少有一个元素   head.prev不会报错
                node.next=head;
                head.prev = node;
                head=node;
            }else {//非空头插
                head=node;
                last=node;
            }

            return;
        }
        //index=size即尾插，单独处理会更方便
        if(index==size()) {
            add(e);
            return;
        }

        //1.先找到待插入位置的前驱结点，从head开始，需要向后跳index-1步
        MyListNode prev=head;
        for(int i=0;i<index-1;i++) {
            prev=prev.next;
        }
        MyListNode next=prev.next;
        //插入node
        node.prev=prev;
        node.next=next;
        prev.next=node;
        next.prev=node;

    }

    @Override
    public String remove(int index) {
        if(index<0 || index>=size()) {
            throw new ArrayIndexOutOfBoundsException("下标不合法！");
        }

        //可能的情况
        //index==0 头删
        //index==size()-1 尾删
        //index!=0  && index!=size()-1  中间删
        //size()==1 等价于head.next==null 等价于prev.next==null

        if(size()==1) {
            String e=head.val;
            head=null;
            last=null;
            return e;
        }else if(index==0) {
            //元素个数大于1的头删
            String e=head.val;
            head=head.next;
            head.prev=null;
            return e;
        }else if(index==size()-1) {
            //元素个数大于1的尾删
            String e=last.val;
            last=last.prev;
            last.next=null;
            return e;
        }else {
            //中间删
            MyListNode delete=head;
            for(int i=0;i<index;i++) {
                delete=delete.next;
            }
            String e=delete.val;

            MyListNode prev=delete.prev;
            MyListNode next=delete.next;

            prev.next=next;
            next.prev=prev;

            return e;

        }
    }

    @Override
    public boolean remove(String e) {
        int index=indexOf(e);
        if(index<0) {
            return false;
        }
        remove(index);
        return true;
    }

    @Override
    public String get(int index) {
        if(index<0 || index>=size()) {
            throw new ArrayIndexOutOfBoundsException("下标不合法！");
        }

        MyListNode cur=head;
        for(int i=0;i<index;i++) {
            cur=cur.next;
        }

        return cur.val;
    }

    @Override
    public String set(int index, String e) {
        if(index <0 || index>size()) {
            throw new ArrayIndexOutOfBoundsException("下标不合法！");
        }

        MyListNode cur=head;
        for(int i=0;i<index;i++) {
            cur=cur.next;
        }
        String old=cur.val;

        cur.val=e;
        return old;
    }

    @Override
    public boolean contains(String e) {
        return indexOf(e)>=0;

    }

    @Override
    public int indexOf(String e) {
        //从头查找元素e所在的下标
        int i=0;
        for(MyListNode cur=head;cur!=null;cur=cur.next) {
            if(cur.val.equals(e)) {
                return i;
            }
            i++;
        }
        return -1;
    }

    @Override
    public int lastIndexOf(String e) {
        //从尾查找元素e所在的下标
        int i=size()-1;
        for(MyListNode cur=last;cur!=null;cur=cur.prev) {
            if(cur.val.equals(e)) {
                return i;
            }
            i--;
        }

        return -1;
    }

    @Override
    public void clear() {
        head=null;
        last=null;
    }

    @Override
    public int size() {
        int count=0;
        for(MyListNode cur=head;cur!=null;cur=cur.next) {
            count++;
        }
        return count;
    }

    @Override
    public boolean isEmpty() {

        return size()==0;
    }

    @Override
    public MyIterator iterator() {
        return null;
    }


    @Override
    public String toString() {
        //String是一个不可变对象，反复修改String会生成新的String对象
        //用StringBuilder改善这个问题
        StringBuilder sb=new StringBuilder("[");

        for(MyListNode cur=head;cur!=null;cur=cur.next) {
            sb.append(cur.val);
            if(cur!=last) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();


        //String是一个不可变对象，反复修改String会生成新的String对象
        //用StringBuilder改善这个问题
//        String ans="[";
//
//        MyListNode cur=head;
//        while (cur!=null) {
//            ans=ans+","+cur.val;
//            //String是一个不可变对象，反复修改String会生成新的String对象
//            //用StringBuilder改善这个问题
//            cur=cur.next;
//        }
//        ans=ans+"]";
//        return ans;
    }
}
